#include <stdio.h>
#define MAXLEN 100000
int main(){

	int pathNum, nodeNum, i, j, k, flag, t;
	scanf("%d%d", &pathNum, &nodeNum);
	int path[nodeNum], dist[nodeNum], map[nodeNum][nodeNum];
	for(i = 0;i < nodeNum * nodeNum; i++){
		map[i/nodeNum][i%nodeNum] = MAXLEN;
	}
	for(k = 0;k < pathNum;k++){
		scanf("%d%d", &i, &j);
		scanf("%d", &map[i][j]);
	}
	for(i = 0; i < nodeNum; i++){		//初始化
		if(map[0][i] <MAXLEN){
			path[i] = 0;
			dist[i] = map[0][i];
		}else{
			path[i] = i;
			dist[i] = MAXLEN;
		}
		map[i][i] = 1;		//表示仍然在未找到最短到集合内
	}
do{
	flag = 0;
	for(i = 0; i < nodeNum; i++){
		if(map[i][i]){
			t = i;
			flag = 1;
			break;
		}	
	}
	for(i = 0; i < nodeNum; i++){
		if(map[i][i] && map[t][t] < map[i][i])
			t = i;		//找到集合里当前到原点最短到点
	}
	map[t][t] = 0;
	for(i = 0; i < nodeNum; i++){
		if(map[0][t] + map[t][i] < dist[i]){
			dist[i] = map[0][t] + map[t][i];	
			path[i] = t;
		}
	}
}while(flag);
	for(i = 0;i < nodeNum; i++)
		printf("%d  ",dist[i]);	
}
